package com.yao.sort;

import java.sql.SQLOutput;
import java.util.Arrays;

/**
 * 插入排序，改进选择排序
 * 时间复杂度：O(n^2)
 *
 * @author yaoym
 *
 */
public class InsertDemo {

	/**
	 * 插入排序
	 *
	 * @param up  true：升序
	 * @param arr
	 */
	public static void sort(Integer[] arr, boolean up) {

		for (int i = 1; i < arr.length; i++) {
			int tmp = arr[i];
			int j = i;
			while(j > 0 && (up ? arr[j - 1] > tmp : arr[j - 1] < tmp)) {
				arr[j] = arr[j - 1];
				--j;
			}
			arr[j] = tmp;
		}

	}




	public static void main(String[] args) {
		Integer[] arr = InitData.sortData(10);

		System.out.println("--插入排序前--");
		for (int i : arr) {
			System.out.print(i + "\t");
		}
		System.out.println();

		sort(arr, true);

		System.out.println("--插入排序后--");
		for (int i : arr) {
			System.out.print(i + "\t");
		}
	}
}
